Data of a graph structure with nodes and edges representing connection relationships between the nodes (hereinafter, which may be simply referred to as “graph data”) is often used to express a real world model on a computer. Graph data is generally described in accordance with a standardized format such as the resource description framework (RDF), and stored in a database termed a “graph repository”. A part or whole of the graph data stored in a graph repository is called by various kinds of application programs for use. Companies in the industry have conducted research and development on software for handling such graph data.
As a background art in the field, Japanese Unexamined Patent Publication No. 2010-256978 (Patent Document 1) discloses a configuration data verification device for facilitating verification of configuration data. The device includes: a relation graph generation unit which extracts dependency relation between components constituting a system from the configuration data of the system and generates a relation graph representing the dependency relation; and a relation graph verification unit which verifies validity of the configuration data on the basis of a reference relation graph provided in advance and the generated relation graph. In the case where the reference relation graph and the generated relation graph are identical in type, the relation graph verification unit determines that the configuration data is valid; otherwise, it determines that the configuration data is invalid.
As another background art, Japanese Unexamined Patent Publication No. 2007-026210 (Patent Document 2) discloses an improved tree display program. According to the program, when a node 4 is designated as a display target by a user from a tree being developed/displayed from an actual root node 1 positioned in an uppermost layer in a tree structure, a tree structure in a similar form when viewed as a non-directed graph is formed and displayed in which the node 4 is disposed in the uppermost layer as a virtual root node. That a node 2 is a parent node of the node 4 is shown by adding an arrow icon 40, in a prescribed direction, to a leader line of the node 2. The relative positional relation between the virtual root node 4 and the actual root node 1 is shown by adding an arrow icon 42, in a prescribed direction, on the path from the virtual root node 4 to the actual root node 1.
As yet another background art, Japanese Unexamined Patent Publication No. 2003-030227 (Patent Document 3) discloses a method capable of handling data aggregates of various types unitarily and capable of dynamically changing the data aggregate and the data structure by reflecting an interaction from a user in the event of the preprocessing for the data mining. The method includes the steps of: creating, from XML data, a hierarchical unit tree as a tree structure in which attributes of the XML data are set as a leaf node and a non-leaf node, a relationship between the attributes without including an attribute value is expressed, and a redundant parent-child relationship between the nodes is optimized by merging; adding a change to the hierarchical unit tree; and converting the XML data so as to reflect the change added to the hierarchical unit tree.
As yet another background art, Japanese Patent No. 3137590 (Patent Document 4) discloses a manufacturing procedure determining system, wherein when an element process has been given, node connection means produces an initial graph. Initially-required node selection means selects required nodes, and initial graph producing means produces the initial graph, composed of nodes and oriented branches, corresponding to each element process. Dependency graph producing means deconstructs the initial graph to produce a dependency graph. Process expression tree producing means deconstructs the dependency graph so as to produce a process expression tree for expressing a manufacturing procedure which can be executed.
As yet another background art, Japanese Unexamined Patent Publication No. 2001-142937 (Patent Document 5) discloses a method for checking the correctness of scheduling of a circuit and a method for verifying a schedule of a circuit against a behavioral description of the circuit. The method for checking the correctness of scheduling of a circuit, where a schedule for the circuit is obtained from a behavioral description, includes the steps of: extracting loop invariants to determine a sufficient set of acyclic threads when loops are present in the circuit; performing symbolic simulation to extract the loop invariants; and proving equivalence of the acyclic threads. The method for verifying a schedule of a circuit against a behavioral description of the circuit includes the steps of: selecting a schedule thread of execution from the schedule where a thread may include loops; identifying a corresponding behavior thread from the behavioral description; proving unconditional equivalence of the schedule thread and the behavior thread; and repeating the above steps for all threads of execution.
As yet another background art, Japanese Unexamined Patent Publication No. 5-233298 (Patent Document 6) provides a ring isomorphism determination system capable of efficiently checking the existence of a bijective homomorphism using a computer when two rings are finite-dimensional over a field. According to this system, bases of the linear spaces are calculated for two arbitrary rings A and B, a linear map φ from the ring A to the ring B is defined, φ* is defined by removing the constant term of the linear map φ, an ideal J is defined from an ideal I on the basis of the determinant (f) of the φ*, the reference relational expression of the rings A and B, and operation as a homomorphism of the linear map φ, and the determination of isomorphism or not is made on the basis of the Groebner basis GJ of the ideal.
As yet another background art, Japanese Unexamined Patent Publication No. 10-154976 (Patent Document 7) provides a tamper-free system which is capable of defending the system against the attack where a physical shock is applied from the outside to the internal circuit to cause the malfunction and the output from the internal circuit is observed to estimate confidential information within the system. The tamper-free system includes means for performing predetermined data conversion processing on data input from the outside to output the processed data, and has its internal circuit entirely protected from the outside by physical means so as to prevent illegal access to the internal information. The system includes means for detecting malfunction of the data conversion processing, and output regulating means for imposing a predetermined regulation on the output from the processing in the case where the malfunction is detected.
As yet another background art, Japanese Unexamined Patent Publication No. 2008-203964 (Patent Document 8) discloses a clustering technique as follows. The technique intelligibly summarizes a causal relation network by clustering a plurality of events while maintaining a correct causal relation between the events. With respect to a causal relation between a plurality of different events extracted from a natural language sentence as a document described in natural language, a cluster object selecting unit selects, as an object of clustering, an event group of events which have some of the constituent words identical to each other and also have a common cause or result event, and a causal relation storage unit stores a causal relation graph having a data structure in which only the causal relations common to all the events as the object of clustering are integrated. The complexity of the structure of the causal relation graph is digitized as a clustering score, and an event cluster evaluation unit clusters the event group selected by the cluster object selecting unit so as to minimize the clustering score.